re:Inventのビンゴ大会で使える、確率予測付きビンゴシミュレーターをRustで作ってみた

こんばんは、リテールアプリ共創部のmorimorikochanです。

先日、re:Inventのビンゴ大会に参加しました。

https://dev.classmethod.jp/articles/re-invent2024-bingo-act128/

ビンゴをやっている最中にふと、"自分のこのカード、今の局面でどのぐらいBINGOになりやすいんやろうか？" と感じました。
だいぶ早い段階でリーチになっているような気がするけどそれは自分の感覚的なものでしかなく、他の参加者は100人を超えているのでどの程度自分が有利な場面にいるのか全くわかりません。

せっかくなので、RustでビンゴシミュレーターとN手先にBINGOになる確率の計算を実装してみたので、同じようなことを考えた人向けに共有したいと思います。

できたもの

あらかじめ自分の手元のビンゴカードをプログラムの入力として与え、選ばれた数字を入力していきます。
そうするとプログラム内の仮想ビンゴカードが変化し、あと何手先で何%の確率でBINGOになるかを算出してくれます。
これで自分のビンゴカードがあとどのぐらいでBINGOになるのかだいたいの予想がつくようになりますね。
来年以降のre:Inventのビンゴ大会で無双できるかも？しれません（できません）

これ以降は、Rustの実装上のポイントや勉強になった部分について解説していきます。

コード

https://github.com/diggymo/bingo-rs

ポイント

fmt::Displayトレイトの実装

プログラムではビンゴカードを表す構造体BingoCardを用意しています。
ビンゴカードをコマンドラインに表示するために、main関数のループ内で直接print!で出力することもできますが、main関数が肥大化するのでBingoCard構造体に対してfmt::Displayトレイトを実装し、UIに関連するロジックをmain関数から分離させています。

https://github.com/diggymo/bingo-rs/blob/ae3c042a5edb5d76c16928e5a02581a3d0cff4dc/src/main.rs#L16-L36

BINGOの判定はシンプルにハードコード

プログラムでは現在のビンゴカードがBINGOになっているかどうか判定する必要があります。
ルールだと"縦・横・斜めに1直線で5つの数字が選択されていればBINGO"ですが、これをプログラムで綺麗に表現すると意外とコードが長くなりますし、可読性が悪いと私は感じました。

fn check_exists_any_line(card: &BingoCard) -> bool {
    for i in 0..5 {
        // 行と列をチェック
        let mut is_bingo_for_row = true;
        for j in 0..5 {
            if !card.state[i][j] {
                is_bingo_for_row = false;
                break;
            }
        }
        if is_bingo_for_row {
            return true;
        }

        let mut is_bingo_for_column = true;
        for j in 0..5 {
            if !card.state[j][i] {
                is_bingo_for_column = false;
                break;
            }
        }
        if is_bingo_for_column {
            return true;
        }
    }

    // ななめをチェック1
    let mut is_bingo_for_slant = true;
    for i in 0..5 {
        if !card.state[i][i] {
            is_bingo_for_slant = false;
            break;
        }
    }
    if is_bingo_for_slant {
        return true;
    }

    // ななめをチェック2
    let mut is_bingo_for_slant_reverse = true;
    for i in 0..5 {
        if !card.state[i][4 - i] {
            is_bingo_for_slant_reverse = false;
            break;
        }
    }
    if is_bingo_for_slant_reverse {
        return true;
    }

    return false;
}

そこで、たかだか12パターンのチェックなので配列で全パターンを列挙してチェックさせています。

https://github.com/diggymo/bingo-rs/blob/ae3c042a5edb5d76c16928e5a02581a3d0cff4dc/src/main.rs#L111-L124

https://github.com/diggymo/bingo-rs/blob/ae3c042a5edb5d76c16928e5a02581a3d0cff4dc/src/main.rs#L225-L233

こっちの方がコードも短く意図が伝わりやすいと私は感じました。
また、プログラムの正確性もある程度担保しやすいと思います。
（以前、競プロをやっている知り合いの人に、この考え方を教えてもらったのですが役立ちました。）

VecよりもHashSetを使って計算量を削減

1手先のBINGOの確率を計算する際には、"もし次にある数字が選ばれた場合、BINGOになるかどうか"というチェックを、選ばれうる全数字に対して行なっています。
2手先を読む場合はさらに選ばれうる全数字に対して行い、3手先はさらに選ばれうる全数字に対して行います。
ビンゴの序盤では、"選ばれうる全数字"が75程度の状態のため計算量が劇的に爆発してしまうことが予想されるので、計算量には注意してこの処理を実装しました。

その1つとして、VecよりもHashSetを多用しました。
Vecは可変長のリストであるため、"任意のデータが要素内のいずれかに一致しているかどうかチェック"するためには先頭から要素を洗っていく必要があり、計算量が O(n)になってしまいます。

対してHashSetでは要素のハッシュで比較しているため、計算量が O(1)になり前述のチェックが高速になります。

https://github.com/diggymo/bingo-rs/blob/ae3c042a5edb5d76c16928e5a02581a3d0cff4dc/src/main.rs#L155-L188

本当はbingo_line_listもVec<HashSet<i32>>ではなくHashSet<HashSet<i32>>で定義したかったのですが、HashSet<i32>に対してEqトレイトとHashトレイトを定義する必要があり大変そうだと思ったので諦めました。（どうせこの変数はHashSetにしても全要素舐めるので、恩恵はないです）

また、HashSetを使うと包含関係を簡単に確認できるis_subset()関数を使うことができ、予期せずHashSetの恩恵を受けることができました。

3手先を超えると処理時間が長すぎる問題

このプログラム、実は3手先までしか計算できていません。
4手先以上を計算させようとすると、手元のPCでは確率が表示されるまで3分以上かかってしまいました。
実際にビンゴ大会で運用することを考えると、この間に次の数字が読み上げられてしまうため使い物にならないことが予想されます。そのため、意図的に3手先までしか計算させていません

処理時間が長い原因はいくつかあります。

計算結果を再利用していない

このプログラムでは1手先の全パターンの計算が終わったら2手先の計算を始め、終わったら3手先、というように処理をしていますが、N手先の計算にはN-1手先の計算の結果を一切使っていません。
なので、N手先の計算時には、N-1手先ですでに計算したパターンを再度計算してしまっています。
以下の例で言うと、1手先計算時にすでに1~75までのパターンでBINGO可否を計算したにもかかわらず、2手先でも再度1手先の計算を行なってしまっています。

1手先の計算完了イメージ

2手先の計算完了イメージ

これは処理時間を悪化させる大きな一因になっていると思います。

現在は深さ優先で計算をしていますが、プログラムの構造を変えて幅優先で処理をしていき、各手先の計算が終わった時点で随時計算結果を出力していけば無駄な計算が発生しないはずだと考えてます。

処理の打ち切りをしていない

BINGOになったパターンの処理の打ち切りもしていません。
上記の"2手先の計算完了イメージ"の例で言うと、1手目が4だった場合その時点でBINGOになるため、2手目に何がきたとしてもBINGOのままです。
なので本来その場合は2手目の計算をスキップすることができるはずです

並列化していない

現在はシングルスレッドで計算させていますが、
以前紹介したようにRayonを使ってマルチスレッドに処理をすると処理時間が改善される見込みがあります。

前述の通り、幅優先探索に変更した場合はどこまでの深さ（=手先）になったらどのぐらいの幅を分割して各スレッドに計算を命令させるかによって処理時間が大きく変わりそうですね

感想

• 来年のre:Inventのビンゴ大会に参加すればこのツールで無双できる....訳ではないですね
  • 結局最初にBINGOになるためには、他の参加者よりも早くBINGOになる必要があり、その可能性を計算しようとすると他の参加者の人数や確率分布を使って計算しなければなりません。
    • BINGOになるまでの回数は正規分布ではないようですし思ったより大変そうです
• 競技プログラミングっぽいなーと感じていました
• 実は当初もっと簡単に計算できる考え方を思い付いていたのですが、実装後に間違っていることに気づき凹んでました
  • 確率が100%を超えていて破綻していることに気づきました🥺
• 気が向けば、処理時間が遅い問題を解決させたいと思います